package competition;

import org.omg.PortableInterceptor.INACTIVE;

import java.math.BigInteger;
import java.util.*;

/**
 * @BelongsProject: LeetCode
 * @BelongsPackage: competition
 * @Author: 江岸
 * @CreateTime: 2021-04-04 10:23
 * @Description:
 */
public class Week235 {
    public static void main(String[] args) {
        int[] a = {5, 1, 2, 3, 4};
        int[] b = {100, 2, 3, 4, 5};
        System.out.println(new Week235().minAbsoluteSumDiff(a, b));

    }

    public String truncateSentence(String s, int k) {
        String[] s1 = s.split(" ");
        String res = "";
        for (int i = 0; i < k; i++) {
            res = res + s1[i] + " ";
        }
        return res.substring(0, res.length() - 1);
    }


    /**
     * 给你用户在 LeetCode 的操作日志，和一个整数 k 。日志用一个二维整数数组 logs 表示，其中每个 logs[i] = [IDi, timei] 表示 ID 为 IDi 的用户在 timei 分钟时执行了某个操作。
     * <p>
     * 多个用户 可以同时执行操作，单个用户可以在同一分钟内执行 多个操作 。
     * <p>
     * 指定用户的 用户活跃分钟数（user active minutes，UAM） 定义为用户对 LeetCode 执行操作的 唯一分钟数 。 即使一分钟内执行多个操作，也只能按一分钟计数。
     * <p>
     * 请你统计用户活跃分钟数的分布情况，统计结果是一个长度为 k 且 下标从 1 开始计数 的数组 answer ，对于每个 j（1 <= j <= k），answer[j] 表示 用户活跃分钟数 等于 j 的用户数。
     * <p>
     * 返回上面描述的答案数组 answer 。
     */
    public int[] findingUsersActiveMinutes(int[][] logs, int k) {
        //存放 id + 操作的具体分钟
        HashMap<Integer, Set<Integer>> map = new HashMap<>();
        for (int i = 0; i < logs.length; i++) {
            map.computeIfAbsent(logs[i][0], key -> new HashSet<>()).add(logs[i][1]);
        }
        int[] ints = new int[k];
        for (Set<Integer> value : map.values()) {
            int size = value.size();
            ints[size - 1] += 1;
        }
        return ints;
    }


    /**
     * 给你两个正整数数组 nums1 和 nums2 ，数组的长度都是 n 。
     * <p>
     * 数组 nums1 和 nums2 的 绝对差值和 定义为所有 |nums1[i] - nums2[i]|（0 <= i < n）的 总和（下标从 0 开始）。
     * <p>
     * 你可以选用 nums1 中的 任意一个 元素来替换 nums1 中的 至多 一个元素，以 最小化 绝对差值和。
     * <p>
     * 在替换数组 nums1 中最多一个元素 之后 ，返回最小绝对差值和。因为答案可能很大，所以需要对 109 + 7 取余 后返回。
     * <p>
     * |x| 定义为：
     * <p>
     * 如果 x >= 0 ，值为 x ，或者
     * 如果 x <= 0 ，值为 -x
     */

    public int minAbsoluteSumDiff(int[] nums1, int[] nums2) {
        long count = 0;
        int[] temp = new int[nums1.length];
        TreeSet<Integer> treeSet = new TreeSet<>();
        for (int i = 0; i < nums1.length; i++) {
            int abs = Math.abs(nums1[i] - nums2[i]);
            temp[i] = abs;
            count += abs;
            treeSet.add(nums1[i]);
        }
        int change = 0;
        for (int i = 0; i < nums1.length; i++) {
            int min;
            if (treeSet.contains(nums2[i])) {
                min = 0;
            }else {
                int i1 = treeSet.lower(nums2[i]) != null ? treeSet.lower(nums2[i]) : nums1[i];
                int i2 = treeSet.higher(nums2[i]) != null ? treeSet.higher(nums2[i]) : nums1[i];
                min = Math.min(Math.abs(i1 - nums2[i]), Math.abs(i2 - nums2[i]));
            }
            change = Math.max(change, temp[i] - min);
        }
        return (int)((count - change) % 1000000007);
    }


    /**
     *
     * 给你一个由正整数组成的数组 nums 。
     *
     * 数字序列的 最大公约数 定义为序列中所有整数的共有约数中的最大整数。
     *
     *     例如，序列 [4,6,16] 的最大公约数是 2 。
     *
     * 数组的一个 子序列 本质是一个序列，可以通过删除数组中的某些元素（或者不删除）得到。
     *
     *     例如，[2,5,10] 是 [1,2,1,2,4,1,5,10] 的一个子序列。
     *
     * 计算并返回 nums 的所有 非空 子序列中 不同 最大公约数的 数目 。
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/number-of-different-subsequences-gcds
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     * 对于每个可能的公约数i，设arr为nums中一个子数组，里面每个元素都是i的倍数，他们的公共最大公约数为commonGCD，如果commonGCD为i就找到了一个。
     * arr = [6， 12， 18], i = 3, commonGCD = 6, 所以i=3不算，i=6才算
     *
     * 作者：avlgood2018
     * 链接：https://leetcode-cn.com/problems/number-of-different-subsequences-gcds/solution/mei-ju-mei-ge-ke-neng-de-gong-yue-shu-by-rsd3/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */
    public int countDifferentSubsequenceGCDs(int[] nums) {
        boolean[] visited = new boolean[200005];
        int max = Integer.MIN_VALUE;
        for (int num : nums) {
            visited[num] = true;
            max = Math.max(max, num);
        }
        int count = 0;
        // 公约数可能的范围【1, max】
        for (int i = 1; i <= max; i++) {
            int commonGCD = -1;
            // 检查所有i的倍数
            for (int j = i; j <= max; j += i) {
                if (visited[j]) {
                    if (commonGCD == -1) {
                        commonGCD = j;
                    } else {
                        commonGCD = gcd(commonGCD, j);
                    }
                }
            }
            if (i == commonGCD) {
                count++;
            }
        }
        return count;
    }

    private int gcd(int x, int y) {
        if (x == 0) {
            return y;
        }
        return gcd(y % x, x);
    }


}
